# -*- coding: utf-8 -*-

"""剑指 Offer II 025. 链表中的两数相加
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：
输入：l1 = [0], l2 = [0]
输出：[0]

提示：
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """首先想到的是翻转l1，l2；从头（低位）到尾（高位）遍历，再辅以进位，计算形成新链表；翻转新链表。
    但是进阶既然提到如果不翻转，怎么处理？
    目前想到的，先尾对齐，在长链表中找到短链表的位置；再遍历求和，将对应位置的求和结果存入数组；逆序遍历数组，形成结果数组；遍历数组，生成新链表并返回"""
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head1, head2 = l1, l2
        
        length1, length2 = 0, 0
        while l1:
            length1 += 1
            l1 = l1.next
        while l2:
            length2 += 1
            l2 = l2.next
        
        arr = []
        if length1 > length2:
            while length1 > length2:
                arr.append(head1.val)
                length1 -= 1
                if head1:
                    head1 = head1.next
        elif length1 < length2:
            while length1 < length2:
                arr.append(head2.val)
                length2 -= 1
                if head2:
                    head2 = head2.next
        
        while head1:
            arr.append(head1.val+head2.val)
            head1 = head1.next
            head2 = head2.next
        
        rs = [0 for _ in range(len(arr)+1)]
        ca = 0
        for i in range(-1, -(len(arr)+1), -1):
            ca, rs[i] = (arr[i]+ca)//10, (arr[i]+ca)%10
        
        if ca:
            rs[0] = ca
        else:
            rs = rs[1:]

        sums_li = ListNode()
        tail = sums_li
        for n in rs:
            tail.next = ListNode(n)
            tail = tail.next
        
        return sums_li.next


if __name__ == '__main__':
    so = Solution()
    head1 = ListNode(7, ListNode(2, ListNode(4, ListNode(3))))
    head2 = ListNode(5, ListNode(6, ListNode(4)))

    print(so.addTwoNumbers(head1, head2).val)
